Data packet transmission systems have become commonplace, from local area networks to networks which are national or even international in scope. When such data transmission services are provided by a common carrier, it is necessary to bill each customer for the service received by that customer. Moreover, it is highly desirable to provide usage sensitive billing for data transmission services provided over such a common carrier transmission network. Such networks comprise a plurality of geographically dispersed switching nodes connected together so as to provide multipath routes between a much larger plurality of customer stations connected to the closest switching node. One such system is shown in the co-pending application of S. J. Colestani, U.S. Ser. No. 326,027, filed Mar. 20, 1989, and assigned to applicant's assignee now U.S. Pat. No. 5,050,162, issued Sep. 17, 1991.
It is relatively simple to generate a billing message when a transmitted packet arrives at the switching point closest to the receiving station. Since each transmitted packet includes a header with both the source address and the destination address included, these two addresses need only be combined with a packet length (if the packets are variable in size). The two addresses can be used to calculate the length of the route and hence the number of packet message charging units to be applied for that route. This charge unit count is then multiplied by the packet count to obtain the total charging unit count which, in turn, can be multiplied by a per unit charge to obtain the billing amount. For large transmission networks including a large plurality of switching nodes and stations, the number of such billing messages generated in a unit time is extremely large. One serious problem with providing usage sensitive billing for such large networks is the difficulty of processing the billing messages fast enough to avoid backup and loss of some of the messages. A critical bottleneck in such billing processing is the time required to search for and retrieve the proper customer account to be updated by the received billing message.
Information or data stored in a computer controlled storage mechanism can be retrieved by searching for a particular value in the stored records. The record or records with matching values are then retrieved. Such searching techniques require repeated access or probes into the storage mechanism to perform value comparisons. In large storage and retrieval systems requiring frequent accesses, such linear or sequential searching often requires more time than is available for the task.
A well-known and much faster method for storing and retrieving information from computer store involves the use of so-called "hashing" techniques. These techniques are also sometimes called scatter-storage or key-transformation techniques. In a system using hashing, a portion of the data record called a key is operated upon (by a hashing function) to produce a storage address in the assigned storage space (called the hash table). This storage address is then used to access the desired storage location directly with far fewer storage accesses or probes than are required for sequential searching. The storage location at the computed address can contain the data record itself or can contain a pointer to the location of the data record for indirect addressing. The fundamentals of hashing techniques are described in the classic text by D. Knuth entitled The Art of Computer Programming, Volume 3, Sorting and Searching, pages 506-549, Addison-Wesley, Reading, Mass., 1973.
Hashing functions are designed to translate the universe of key values into addresses uniformly distributed throughout the hash table. Typical types of hashing functions include truncation, folding, transposition and modulo arithmetic. A major disadvantage of hashing techniques is that more than one key can translate into the same storage address, causing "collisions" in storage and retrieval operations. Some sort of collision-resolution strategy must therefore be provided to find a readily recoverable place to store all of the records hashing to the same address. Moreover, such collided records must themselves be recoverable in a reasonable amount of time so as not to lose all of the increased searching speed gained with the hashing technique.
One well-known storage strategy for rapid retrieval is to form a binary tree structure out of all of the collided data records. The bit positions of the unhashed key value can be used to control the rapid stepping through the binary tree to the desired record without examining any other records in the tree.
It is therefore desirable to utilize a hashing technique for storing and retrieving customer records in a customer billing system and to resolve collisions in the hashing operation by the use a binary tree structure to store customer records hashing to the same address in the hash table. While this approach produces a very fast storage and retrieval system, it may still not be fast enough to accommodate a real-time customer billing system for a large packet transmission network utilizing usage sensitive billing.